//
//  NSArray+ZXCategory.m
//  MobileCaiLocal
//
//  Created by simon on 2020/6/4.
//  Copyright © 2020 com.Chs. All rights reserved.
//

#import "NSArray+ZXCategory.h"

@implementation NSArray (ZXCategory)


- (NSArray *)zx_where:(BOOL(^)(id obj))testBlock
{
    if (!self) {
        return nil;
    }else if (self && self.count==0)
    {
        return self;
    }
    NSMutableArray *arr = [NSMutableArray arrayWithCapacity:self.count];
    for (id obj in self) {
        BOOL flag =  testBlock(obj);
        if (flag) {
            [arr addObject:obj];
        }
    }
    return arr;
}

- (id)zx_map:(id(^)(id obj))fBlock
{
    if (!self) {
        return nil;
    }else if (self && self.count==0)
    {
        return self;
    }
    else if (!fBlock)
    {
       return self;
    }
    NSMutableArray *arr = [NSMutableArray arrayWithCapacity:self.count];
    for (id obj in self) {
        id e =  fBlock(obj);
        if (e) {
            [arr addObject:e];
        }
    }
    return arr;
}


- (BOOL)zx_every:(BOOL(^)(id obj))testBlock
{
    if (!self || self.count == 0) {
        return NO;
    }
    for (id obj in self) {
        if (!testBlock(obj)) return NO;
    }
    return YES;
}



- (BOOL)zx_any:(BOOL(^)(id obj))testBlock
{
    if (!self || self.count == 0) {
        return NO;
    }
    for (id obj in self) {
        BOOL flag =  testBlock(obj);
        if (flag) {
            return YES;
        }
    }
    return NO;
}


- (BOOL)zx_isEmpty
{
    if (self != nil && ![self isKindOfClass:[NSNull class]] && self.count != 0){
        return NO;
    }
    return YES;
}

- (void)zx_forEach:(void(^)(id obj))fBlock
{
    for (id obj in self) {
        fBlock(obj);
    }
}


#pragma mark - 查找算法

#pragma mark-二分查找
- (BOOL)zx_binarySearchWithNumber:(id)obj
{
    NSInteger low = 0;
    NSInteger high = self.count -1;
    double objectNum = [obj doubleValue];
    while (low <= high) {
        NSInteger mid = (low + high)/2;
        double midValue = [self[mid] doubleValue];
        if (objectNum  == midValue) {
            return YES;
        }
        else if (objectNum < midValue) {
            high = mid -1;
        }
        else{
            low = mid +1;
        }
    }
    return NO;
}

- (BOOL)zx_binarySearchWithObject:(id)obj usingComparator:(NSComparator NS_NOESCAPE)cmp{
    NSInteger left = 0;
    NSInteger right = self.count -1;
    while (left <= right) {
        NSInteger mid = (right + left)/2;
        id midObj = self[mid];
        NSComparisonResult comparisonResult = cmp(obj,midObj);
        if (comparisonResult == NSOrderedSame) {
            return YES;
        }
        if (comparisonResult == NSOrderedAscending) {
            left = mid +1;
        }
        if (comparisonResult == NSOrderedDescending) {
            right = mid -1;
        }
    }
    return NO;
}


- (NSInteger)zx_binarySearchIndexOfObjectNumber:(id)obj
{
    NSInteger low = 0;
    NSInteger high = self.count -1;
    double objectNum = [obj doubleValue];
    while (low <= high) {
        NSInteger mid = (low + high)/2;
        double midValue = [self[mid] doubleValue];
        if (objectNum  == midValue) {
            return mid;
        }
        else if (objectNum < midValue) {
            high = mid -1;
        }
        else{
            low = mid +1;
        }
    }
    return NSNotFound;
}

#pragma mark-插值查找

- (BOOL)zx_interpolationSearchWithNumber:(id)obj{
    NSInteger low = 0;
    NSInteger high = self.count -1;
    double objectNum = [obj doubleValue];
    while (low <= high) {
        double leftNum = [self[low] doubleValue];
        double rightNum = [self[high] doubleValue];
        double a = (objectNum - leftNum)/(rightNum - leftNum);
        NSInteger mid = low + (NSInteger)((high - low) * a);
        double midValue = [self[mid] doubleValue];
        if (objectNum  == midValue) {
            return YES;
        }
        else if (objectNum < midValue) {
            high = mid -1;
        }
        else{
            low = mid +1;
        }
    }
    return NO;
}


#pragma mark - 排序算法

#pragma mark-冒泡排序

- (NSArray *)zx_bubbleSort:(int)orderType  usingComparator:(NSComparator NS_NOESCAPE)cmptr{
    NSMutableArray *arr;
    if ([self isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)self;
    }else{
        arr = [self mutableCopy];
    }
    NSUInteger n = arr.count;
    
    if (orderType == 0) {
        for (int i = 0; i< n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (cmptr(arr[j],arr[j+1]) == NSOrderedDescending) {
                    [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                }
            }
        }
    }else{
        for (int i = 0; i< n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (cmptr(arr[j],arr[j+1]) == NSOrderedAscending) {
                    [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                }
            }
        }
    }
    return arr;
}

#pragma mark-选择排序

- (NSArray *)zx_selectSort:(int)orderType  usingComparator:(NSComparator NS_NOESCAPE)cmptr{
    NSMutableArray *arr;
    if ([self isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)self;
    }else{
        arr = [self mutableCopy];
    }
    NSUInteger n = arr.count;
    //升序
    if (orderType == 0) {
        for (int i = 0; i<n-1; i++) {
            ///最小值
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (cmptr(arr[min],arr[j]) == NSOrderedDescending) {
                    min = j;
                }
            }
            if (min != i) {
                [arr exchangeObjectAtIndex:i withObjectAtIndex:min];
            }
        }
    }else{
        
    }
    return arr;
}


#pragma mark-插入排序

- (NSArray *)zx_insetSort:(int)orderType  usingComparator:(NSComparator NS_NOESCAPE)cmptr
{
    NSMutableArray *arr;
    if ([self isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)self;
    }else{
        arr = [self mutableCopy];
    }
    int n = (int)arr.count;
    if (orderType == 0) {
        for (int i = 1; i< n; i++) {
            id obj = arr[i];
            for (int j =0; j<i; j++) {
                if (cmptr(obj,arr[j])== NSOrderedAscending)
                {
                    [arr removeObjectAtIndex:i];
                    [arr insertObject:obj atIndex:j];
                    ///对当前元素前面有序表进行待插入位置查找，并进行移动。找到之后那后面的不需要再遍历查找了，因为之前的已经是有序了。
                    break;
                }
            }
        }
    }else{
        for (int i = 1; i< n; i++) {
            id obj = arr[i];
            for (int j =0; j<i; j++) {
                if (cmptr(obj,arr[j]) == NSOrderedDescending)
                {
                    [arr removeObjectAtIndex:i];
                    [arr insertObject:obj atIndex:j];
                    break;
                }
            }
        }
    }
    return arr;
}

- (NSArray *)zx_insetSort:(int)orderType
                      low:(int)low
                     high:(int)high
          usingComparator:(NSComparator NS_NOESCAPE)cmptr{
    
    NSMutableArray *arr;
    if ([self isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)self;
    }else{
        arr = [self mutableCopy];
    }
    if (orderType == 0) {
        for (int i = low+1; i< high+1; i++) {
            id obj = arr[i];
            for (int j =low; j<i; j++) {
                if (cmptr(obj,arr[j])== NSOrderedAscending)
                {
                    [arr removeObjectAtIndex:i];
                    [arr insertObject:obj atIndex:j];
                    break;
                }
            }
        }
    }else{
        for (int i = low+1; i< high+1; i++) {
            id obj = arr[i];
            for (int j =low; j<i; j++) {
                if (cmptr(obj,arr[j]) == NSOrderedDescending)
                {
                    [arr removeObjectAtIndex:i];
                    [arr insertObject:obj atIndex:j];
                    break;
                }
            }
        }
    }
    return arr;
}


#pragma mark-希尔排序

- (NSArray *)zx_shellSort:(int)orderType
          usingComparator:(NSComparator NS_NOESCAPE)cmptr{
    NSMutableArray *arr;
    if ([self isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)self;
    }else{
        arr = [self mutableCopy];
    }
    NSUInteger n = arr.count;
    
    int step = (int)arr.count/2;
    while (step>0) {
        for (int i=0; i<step; i++) {
            int j = i + step;
            
            while (j<n) {
                id obj = arr[j];
                int k = i;
                while (k<j) {
                    if (orderType == 0){
                        if (cmptr(obj,arr[k])== NSOrderedAscending) {
                            [arr removeObjectAtIndex:j];
                            [arr insertObject:obj atIndex:k];
                            break;
                        }
                    }else{
                        if (cmptr(obj,arr[k])== NSOrderedDescending) {
                            [arr removeObjectAtIndex:j];
                            [arr insertObject:obj atIndex:k];
                            break;
                        }
                    }
                    k += step;
                }
                j += step;
            }
        }
        step = step/2;
    }
    return arr;
}


#pragma mark-快速排序

+ (NSArray *)zx_quickSort:(NSArray *)array
          usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr{
    NSMutableArray *arr;
    if ([array isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)array;
    }else{
        arr = [array mutableCopy];
    }
    NSArray *a = [NSArray zx_quickSortWithArr:arr low:0 high:(int)(arr.count-1) usingComparator:cmptr];
    return a;
}

- (NSArray *)zx_quickSortUsingComparator:(NSComparisonResult(^)(id obj, id key))cmptr{
    return [NSArray zx_quickSort:self usingComparator:cmptr];
}

+ (NSArray *)zx_quickSortWithArr:(NSMutableArray *)arr
                             low:(int)low
                            high:(int)high
                 usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr
{
    if (low >= high) {
        return arr;
    }
    ///递归比较消耗资源。
    ///优化：设置阈值,在数组元素较少时不再递归，而是采用插入排序.
    if (arr.count <= 5 || high-low < 5) {
        NSArray *a = [arr zx_insetSort:0 low:low high:high usingComparator:cmptr];
        return a;
    }
    
    ///基准值取值，若所取基准值为序列中的最大或最小值，那么每趟划分后，基准值的一侧将会出现没有元素的情况，就相当于每趟只完成了一个元素的排序，那么快速排序的时间复杂度此时将达到O（n^2），效率较低。
    ///优化：三位取中法
    id first = [arr firstObject];
    id last = [arr lastObject];
    id center = [arr objectAtIndex:arr.count/2];
    NSArray *flagArray = @[first,center,last];
    NSArray *flagSortArr = [flagArray zx_insetSort:0 low:0 high:2 usingComparator:cmptr];
    id centerObj = [flagSortArr objectAtIndex:1];
    NSUInteger centerObjIndex = [arr indexOfObject:centerObj];
    if (centerObjIndex != 0) {
        [arr exchangeObjectAtIndex:0 withObjectAtIndex:centerObjIndex];
    }
    
    ///进行划分
    int i = [self zx_quickSortPartitionWithArr:arr low:low high:high usingComparator:cmptr];
    ///对前半区进行快速排序
    [self zx_quickSortWithArr:arr low:low high:i-1 usingComparator:cmptr];
    ///对后半区进行快速排序
    [self zx_quickSortWithArr:arr low:i+1 high:high usingComparator:cmptr];
    return arr;
}

///进行划分
///通过两个标志，先从右向左找比基准值小的第一个元素，再从左往右找比基准值大的第一个元素，然后交换两个元素，重复上述过程直到两个标志位相遇，最后再将基准值交换到相遇位置，然后再对左右子序列重复上述过程，直到整个序列完成排序。
+ (int)zx_quickSortPartitionWithArr:(NSMutableArray *)arr
                                low:(int)low
                               high:(int)high
                    usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr
{
    int i = low;
    int j = high;
    id key = arr[i];
    while (i < j) {
        ///从右向左找到比枢轴（基准）元素小的，如果遇到比基准大的则j--继续
        ///while (i<j && [arr[j] intValue] >= [key intValue]) {j--}
        while (i < j && (cmptr(arr[j],key) == NSOrderedDescending||cmptr(arr[j],key) == NSOrderedSame)) {
            j--;
        }
        ///当key是目前最小的数时，会出现i=j的情况，
        if (i == j) {
            break;
        }
        ///比枢轴（基准）元素小的往前移
        arr[i] = arr[j];
        ///从左往右找到比枢轴（基准）元素大的，如果遇到比基准小的则i++继续
        ///while (i<j && [arr[i] intValue] <= [key intValue]) {i++}
        while (i<j && (cmptr(arr[i],key) == NSOrderedAscending||cmptr(arr[i],key) == NSOrderedSame)) {
            i++;
        }
        ///当key是目前最小的数时，会出现i=j的情况，
        if (i == j) {
            break;
        }
        ///比枢轴（基准）元素大的往后移
        arr[j] = arr[i];
    }
    ///最后将基准值交换到相遇位置
    arr[i] = key;
    return i;///划分完后返回枢轴（基准）元素的位置
}


//- (NSArray *)zx_quickSort2UsingComparator:(NSComparisonResult(^)(id obj, id key))cmptr
//{
//    NSArray *sortedArr = [NSArray zx_quickSort2WithArr:self usingComparator:cmptr];
//    return sortedArr;
//}
+ (NSArray *)zx_quickSort2:(NSArray *)array
           usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr{
    if (array.count <= 1) {
        return array;
    }
    id key = [array firstObject];
    NSUInteger n = array.count;
    NSMutableArray *left = [NSMutableArray array];
    NSMutableArray *right = [NSMutableArray array];
    for (int i = 1; i< n; i++) {
        if (cmptr(array[i],key) == NSOrderedDescending) {
            [right addObject:array[i]];
        }else{
            [left addObject:array[i]];
        }
    }
    NSArray *sortedLeft =  [self zx_quickSort2:left usingComparator:cmptr];
    NSArray *sortedRight = [self zx_quickSort2:right usingComparator:cmptr];
    NSMutableArray *sorted = [NSMutableArray arrayWithArray:sortedLeft];
    [sorted addObject:key];
    [sorted addObjectsFromArray:sortedRight];
    return sorted;
}


#pragma mark-堆排序

+ (NSArray *)zx_heapSort:(NSArray *)array
         usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr
{
    NSMutableArray *arr;
    if ([array isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)array;
    }else{
        arr = [array mutableCopy];
    }
    int n = (int)arr.count;
    NSMutableArray *result = [NSMutableArray array];
    while (n>0) {
        [NSArray heapAdjust:arr usingComparator:cmptr];
        [result insertObject:arr.firstObject atIndex:0];
        [arr removeObjectAtIndex:0];
        n = n-1;
    }
    return result;
}

///最大堆
///对于最大堆的构造，通过逆序遍历数组，每次将最大值上浮到父节点中即可。
+ (void)heapAdjust:(NSMutableArray *)arr
   usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr
{
    for (int i =0; i<arr.count; i++) {
        
        int index = (int)arr.count-1-i;
        id top = arr[index];
        int left = 0;
        int right = 0;
        if ((index*2 +1) < arr.count) {
            left = index *2 +1;
        }
        if ((index*2 +2) < arr.count) {
            right = index *2 +2;
        }
        ///进行调整
        if (left>0) {
            if (cmptr(arr[left],top) == NSOrderedDescending)
            {
                arr[index] = arr[left];
                arr[left] = top;
                top = arr[index];
            }
        }
        if (right>0) {
            if (cmptr(arr[right],top) == NSOrderedDescending) {
                arr[index] = arr[right];
                arr[right] = top;
                top = arr[index];
            }
        }
    }
}


#pragma mark - 归并排序

+ (NSArray *)zx_mergeSort:(NSArray *)array
          usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr{
    NSMutableArray *arr;
    if ([array isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)array;
    }else{
        arr = [array mutableCopy];
    }
    [self zx_mergeSort:arr start:0 end:(int)(arr.count-1) usingComparator:cmptr];
    return arr;
}

+ (NSArray *)zx_mergeSort:(NSArray<NSNumber *> *)array
{
    NSMutableArray *arr;
    if ([array isKindOfClass:[NSMutableArray class]]) {
        arr = (NSMutableArray *)array;
    }else{
        arr = [array mutableCopy];
    }
    [self zx_mergeSort:arr start:0 end:(int)(arr.count-1) usingComparator:nil];
    return arr;
}

+ (void)zx_mergeSort:(NSMutableArray<NSNumber *> *)data
               start:(int)start
                 end:(int)end
     usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr
{
    
    ///当start==end时，此时分组里只有一个元素，这是临界点
    if (start < end) {
        ///分成左右两个分组，再进行递归:将data[start..end]均分为data[start..mid]和data[mid+1..end]
        int mid = (start + end) / 2;
        ///左半边分组:递归地对data[start..mid]并进行归并排序
        [self zx_mergeSort:data start:start end:mid usingComparator:cmptr];
        ///右半边分组:递归地对data[mid+1..end]进行归并排序
        [self zx_mergeSort:data start:mid+1 end:end usingComparator:cmptr];

        ///递归之后归并为一个大组；第一个参数是【0，0，1】
        [self zx_merge:data low:start mid:mid high:end usingComparator:cmptr];
    }
}

///第二步：拆分到最后一步，每一个小序列都是单独的元素。我们再把这些元素进行归并
+ (void)zx_merge:(NSMutableArray<NSNumber *> *)data
             low:(int)low
             mid:(int)mid
            high:(int)high
 usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr
{
    ///左边分组的起点i_start,终点i_end,也就是第一个有序序列
    int i_start = low;
    int i_end = mid;
    
    ///右边分组的起点j_start,终点j_end,也就是第二个有序序列
    int j_start = mid+1;
    int j_end = high;
    
    int k = 0;
    
    ///额外空间初始化
    NSMutableArray *array = [NSMutableArray arrayWithCapacity:high-low+1];
    
    ///合并两个有序序列，
    ///比较两个序列，把小的放入额为空间；比较之后会留下剩余元素。
    while (i_start <= i_end && j_start <= j_end) {
        ///当data[i_s]<data[j_s]值时，将较小元素放外额外空间，反之一样。
        if (cmptr) {
            if (cmptr(data[i_start],data[j_start]) == NSOrderedAscending) {
                array[k] = data[i_start];
                k++;
                i_start ++;
            }else{
                array[k] = data[j_start];
                k += 1;
                j_start += 1;
            }
        }else{
            if ([data[i_start]intValue] < [data[j_start]intValue]) {
    //         array[k++] = data[i++];
                array[k] = data[i_start];
                k++;
                i_start ++;
            }else{
                array[k] = data[j_start];
                k += 1;
                j_start += 1;
            }
        }
    }
    ///把剩余元素放在额外空间的最末尾处
    ///i这个序列还有剩余元素
    while (i_start <= i_end) {
        array[k] = data[i_start];
        i_start += 1;
        k += 1;
    }
    ///j这个序列还有剩余元素
    while (j_start <= j_end) {
        array[k] = data[j_start];
        j_start += 1;
        k += 1;
    }
    ///辅助空间数据覆盖到原空间
    for (int i = 0; i<array.count; i++) {
        data[low+i] = array[i];
    }
}





@end


#pragma mark - C方法
/*
 C/C++中如果一个函数接受一个数组作为参数，那么数组将会被退化为指针，是传递数组首个元素的地址，而不是传递整个的数组空间。所以在传递前就需要进行数组长度求解。
 报错：sizeof使用数组作为参数时会返回int*大小（指针的字节数），即使用sizeof测试数组类型的参数大小时得到的并不是整个数组的字节数，而是指针的字节数。
*/
#pragma mark - C冒泡排序

void zx_bubbleSort(int data[_Nullable],int n,int orderType)
{
    int temp;
    if (orderType == 0) {
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (data[j] > data[j+1]) {
                    temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
        }
    }else{
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (data[j] < data[j+1]) {
                    temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
        }
    }
}

#pragma mark - C选择排序
void zx_selectSort(int data[_Nullable],int n,int orderType)
{
    int temp;
    if (orderType == 0){
        for (int i = 0; i < n-1; i++) {
            ///最小值
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (data[min] > data[j]) {
                    min = j;
                }
            }
            if (min != i) {
                temp = data[i];
                data[i] = data[min];
                data[min] = temp;
            }
        }
    }else{
        for (int i = 0; i < n-1; i++) {
            ///最大值
            int max = i;
            for (int j = i+1; j < n; j++) {
                if (data[max] < data[j]) {
                    max = j;
                }
            }
            if (max != i) {
                temp = data[i];
                data[i] = data[max];
                data[max] = temp;
            }
        }
    }
}

#pragma mark - C插入排序

void zx_insetSort(int data[_Nullable],int n){
    
    for (int i = 1; i < n; i++) {
        
        if (data[i] < data[i-1]) {
            
            int temp = data[i];
            for (int j = i-1; j >= 0; j--) {
                if (temp < data[j]) {
                    data[j+1] = data[j];
                    data[j] = temp;
                }
            }
        }
    }
}

#pragma mark - C希尔排序

void zx_shellSort(int data[_Nullable],int n, int delta[_Nullable],int m){
    
    for (int i = 0; i < m; i++) {
        int dk = delta[i];
        
        for (int k = dk; k<n; ++k) {
            if (data[k] < data[k-dk]) {
                int temp = data[k];
                for (int j = k-dk; j >= 0; j -= dk) {
                    if (temp < data[j]) {
                        data[j+dk] = data[j];
                        data[j] = temp;
                    }
                }
            }
        }
    }
}

#pragma mark - C快速排序

int partition(int data[],int low, int high){
    //用data[low]的值作为枢轴元素pivot进行划分
    //使得data[low..i-1]均不大于pivot,dta[i+1..high]均不小于pivot
    int i = low;
    int j = high;
    int pivot = data[low];
    //从数组的两端交替地向中间扫描
    while (i<j) {
        ///比枢轴（基准）元素小的往前移
        while (i<j && data[j] >= pivot) {
            j--;
        }
        data[i] = data[j];
        ///比枢轴（基准）元素大的往后移
        while (i<j && data[i] <= pivot) {
            i++;
        }
        data[j] = data[i];
    }
    data[i] = pivot;
    return i;
}


void zx_quickSort(int data[_Nullable],int low, int high){
    if (low < high) {
        ///进行划分
        int i = partition(data, low, high);
        ///对前半区进行快速排序
        zx_quickSort(data, low, i-1);
        ///对后半区进行快速排序
        zx_quickSort(data, i+1, high);
    }
}

#pragma mark - C归并排序

///将有序子序列data[low..mid-1]和data[mid..high]归并为有序序列data[low..high]
void merge(int data[_Nullable],int low,int mid, int high){
    
    int i = low;
    int i_end = mid;
    
    int j_start = mid+1;
    int j_end = high;
    ///额外空间初始化
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    if (!tmp) {
        exit(0);
    }
    int k = 0;
    ///合并两个有序序列，
    ///比较两个序列，把小的放入额外空间；比较之后会多出来剩余元素。
    while (i <= i_end && j_start <= j_end) {
        if (data[i] < data[j_start]) {
            tmp[k++] = data[i++];
        }else{
            tmp[k++] = data[j_start++];
        }
    }
    ///把剩余元素放在额外空间的最末尾处
    ///i这个序列还有剩余元素
    while (i <= i_end) {
        tmp[k++] = data[i++];
    }
    ///j这个序列还有剩余元素
    while (j_start <= j_end) {
        tmp[k++] = data[j_start++];
    }
    ///辅助空间数据覆盖到原空间
//    i = low; int p = 0;
//    while (p<k) {
//        data[i++]=tmp[p++];
//    }
    for (int i = 0; i<k; i++) {
        data[low+i] = tmp[i];
    }
    free(tmp);
}

void zx_mergeSort(int data[_Nullable],int start, int t)
{
    if (start < t) {
        ///将data[s..t]均分为data[s..mid]和data[mid+1..t]
        ///最后传进来索引差小于2个数的时候s=0，t=1；结束拆分，开始归并；
        int mid = (start + t)/2;
        ///递归地对data[s..mid]进行归并排序
        zx_mergeSort(data, start, mid);
        ///递归地对data[mid+1..t]进行归并排序
        zx_mergeSort(data, mid+1, t);
        ///递归之后归并为一个大组；第一个参数是【0，0，1】
        merge(data, start, mid, t);
    }
}
